﻿/* 11. Write a program that finds the index of given element in a sorted array of integers
 * by using the binary search algorithm. */

using System;

public class BinarySearchAlgorithm
{
    public static void Main()
    {
        int n;
        double[] array;
        double element;
        int index;

        Console.Write("\nThe length of (increasing sorted) array: ");
        n = int.Parse(Console.ReadLine());

        if (0 < n)
        {
            array = new double[n];
            Console.WriteLine();
            for (int i = 0; i < n; i++)
            {
                Console.Write("Array[{0}] = ", i);
                array[i] = double.Parse(Console.ReadLine());
            }

            Console.Write("\nand find the index of the Element: ");
            element = int.Parse(Console.ReadLine());

            if ((element < array[0]) || (array[n - 1] < element))
                index = -1;
            else
                index = BinarySearch(array, element, 0, n);

            if (index == -1)
                Console.WriteLine("\nThe array not contains the element {0} !\n", element);
            else
                Console.WriteLine("\nThe array contains the element {0} on index {1} .\n", element, index);
        }
        else
            Console.WriteLine("\nThe length of array must be natural!\n");
    }

    public static int BinarySearch(double[] array, double element, int startIndex, int endIndex)
    {
        int middleIndex = (startIndex + endIndex) / 2;

        while (startIndex <= endIndex)
        {
            if (array[middleIndex] == element)
                return middleIndex;
            else if (element < array[middleIndex])
                endIndex = middleIndex - 1;
            else
                startIndex = middleIndex + 1;

            middleIndex = (startIndex + endIndex) / 2;
        }

        return -1;
    }
}